import networkx as nx
import random
import math

def simulated_annealing(G, initial_temp, cooling_rate, iterations):
    partition = {node: i for i, node in enumerate(G.nodes)}
    modularity = nx.algorithms.community.modularity(G, [set(G.nodes)])
    best_partition = partition
    best_modularity = modularity
    temp = initial_temp
    for i in range(iterations):
        for node in G.nodes:
            community_choices = list(set(partition.values()))
            new_community = random.choice(community_choices)
            old_community = partition[node]
            partition[node] = new_community
            new_modularity = nx.algorithms.community.modularity(G, list(set([frozenset([node for node, community in partition.items() if community == com]) for com in set(partition.values())])))
            delta_modularity = new_modularity - modularity
            if delta_modularity > 0 or math.exp(delta_modularity / temp) > random.random():
                modularity = new_modularity
                if new_modularity > best_modularity:
                    best_partition = partition.copy()
                    best_modularity = new_modularity
            else:
                partition[node] = old_community  # 撤回变更
        temp *= cooling_rate

    return best_partition, best_modularity

G = nx.Graph()
G.add_nodes_from(range(3885))
while G.number_of_edges() < 7260:
    node1 = random.choice(range(3885))
    node2 = random.choice(range(3885))
    if node1 != node2 and not G.has_edge(node1, node2):
        G.add_edge(node1, node2)

initial_temp = 1.0
cooling_rate = 0.99
iterations = 100
best_partition, best_modularity = simulated_annealing(G, initial_temp, cooling_rate, iterations)

print("Best Partition:", best_partition)
print("Best Modularity:", best_modularity)
